ARC036 D - 偶数メートル

解答

code: python

n, q = map(int, input().split())

class UnionFind:

def __init__(self, n):

def root(self, x):

return x

else:

def union(self, x, y):

x = self.root(x)

y = self.root(y)

if x == y:

return

else:

def same(self, x, y):

return self.root(x) == self.root(y)

# 同じ頂点番号の頂点を 2 つずつ用意して、青、赤に分けておく

# 同じ色の頂点同士は偶数メートルでのみ行き来できる

# 違う色の頂点同士は奇数メートルでのみ行き来できる

uf = UnionFind(2 * (n+1))

for w, x, y, z in wxyz:

if w == 1:

# 同じ色同士を結ぶ

if z % 2 == 0:

# 青

uf.union(2*x, 2*y)

# 赤

uf.union(2*x + 1, 2*y + 1)

# 別の色同士を結ぶ

else:

uf.union(2*x, 2*y + 1)

uf.union(2*x + 1, 2*y)

else:

# 赤だけを見て、同じ連結成分なら、YES, 違かったらNO

if uf.root(2*x + 1) == uf.root(2*y + 1):

print('YES')

else:

print('NO')

テーマ

メモ